package com.captain.lc.动态规划;

/**
 * Des:
 * 01 背包问题
 *
 * @author XL
 * @Date 2021/10/27 9:39
 */
public class Knapsack {

    /**
     * des:
     * 获取最大的值 二维数组
     *
     * @return {@link int }
     * @author captain
     * @date 2021/10/27 9:40
     */
    public static int maxValue(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        //定义dp dp[i][j]: 前i个物品可选 , 最大承重量为j的最大价值是 dp[i][j]
        int len1 = values.length;
        int[] dp = new int[capacity + 1];
        //1件物品  / 0件物品时 , 肯定dp[0][j] = 0 dp[i][0] 时 , 也是为0 , 无需初始化
        for (int i = 1; i <= len1; i++) {
            for (int j = capacity; j >= 1; j--) {
                //dp[i][j]  如果当前 j < weights[i] ,则dp[i][j] = dp[i - 1][j]
                if (j < weights[i - 1]) {
                    dp[j] = dp[j];
                } else {
                    //dp[i][j] 取决于当前物品是否选择, 我可以选, 也可以不选, 取最大的值的情况就可以
                    dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {

        int[] values = new int[]{6, 3, 5, 4, 6};
        int[] weights = new int[]{2, 2, 6, 5, 4};
        int capacity = 10;
        System.out.println(maxValue(values, weights, capacity));
    }

}
